package com.lw.leetcode.test.lfu;

import java.util.*;

/**
 * @Author liw
 * @Date 2021/3/24 13:23
 * @Version 1.0
 */
public class LFU<K, V> {
    private int capacity;
    private Map<K, Node<K, V>> caches;

    public LFU(int size) {
        this.capacity = size;
        caches = new LinkedHashMap<>(size);
    }

    public void put(K key, V value) {
        Node<K, V> node = caches.get(key); //如果新元素
        if (node == null) { //如果超过元素容纳量
            if (caches.size() >= capacity) { //移除count计数最小的那个key
                K leastKey = removeLeastCount();
                caches.remove(leastKey);
            } //创建新节点
            node = new Node<>(key, value, System.nanoTime(), 1);
            caches.put(key, node);
        } else { //已经存在的元素覆盖旧值
            node.setValue(value);
            node.setCount(node.getCount() + 1);
            node.setTime(System.nanoTime());
        }
        sort();
        System.out.println(caches);
    }

    public V get(K key) {
        Node<K, V> node = caches.get(key);
        if (node != null) {
            node.setCount(node.getCount() + 1);
            node.setTime(System.nanoTime());
            sort();
            System.out.println(caches);
            return node.getValue();
        }
        System.out.println(caches);
        return null;
    }

    private K removeLeastCount() {
        Collection<Node<K, V>> values = caches.values();
        Node<K, V> min = Collections.min(values);
        return min.getKey();
    }

    private void sort() {
        List<Map.Entry<K, Node<K, V>>> list = new ArrayList<>(caches.entrySet());
        list.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));

        caches.clear();

        for (Map.Entry<K, Node<K, V>> kNodeEntry : list) {
            caches.put(kNodeEntry.getKey(), kNodeEntry.getValue());
        }

    }

    public static  void main(String[] args) {

        LFU<Integer, String> lruCache = new LFU<>(3);
        lruCache.put(1, "A");
        lruCache.put(2, "B");
        lruCache.put(3, "C");
        lruCache.put(4, "D");
        lruCache.put(5, "E");
        lruCache.put(6, "F");
        lruCache.get(5);
        lruCache.get(6);
        //重新put节点3
        lruCache.put(3,"cc");

        final Map<Integer, Node<Integer, String>> caches =  lruCache.caches;
        for (Map.Entry<Integer, Node<Integer, String>> nodeEntry : caches.entrySet()) {
            System.out.println(nodeEntry.getValue().getValue());
        }
    }


}


